﻿using Common;
using Linguist.Acoustic;
using Linguist.Dictionary;
using Linguist.Language.Grammar;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Linguist.Flat
{
    public partial class FlatLinguist
    {
        /// <summary>
        /// 
        /// This is a nested class that is used to manage the construction of the states in a grammar node. There is one
        /// GState created for each grammar node. The GState is used to collect the entry and exit points for the grammar
        /// node and for connecting up the grammar nodes to each other.
        ///
        /// </summary>
        /// 
        public class GState 
        {
            private FlatLinguist FlatLinguistParent =null;
            private Dictionary<ContextPair, List<ISearchState>> entryPoints = new Dictionary<ContextPair, List<ISearchState>>();
            private Dictionary<ContextPair, List<ISearchState>> exitPoints = new Dictionary<ContextPair, List<ISearchState>>();
            private Dictionary<String, SentenceHMMState> existingStates = new Dictionary<String, SentenceHMMState>();

            private GrammarNode node;

            private List<UnitContext> rightContexts = new List<UnitContext>();
            private List<UnitContext> leftContexts = new List<UnitContext>();
            private List<UnitContext> startingContexts;

            private int exitConnections;
    //        private GrammarArc[] successors = null;


            /// <summary>
            /// Creates a GState for a grammar node
            /// </summary>
            /// <param name="node">the grammar node</param>
            /// <param name="parent"></param>
            public  GState(GrammarNode node, FlatLinguist parent) 
            {
                FlatLinguistParent = parent;
                this.node = node;
                FlatLinguistParent.nodeStateMap.Add(node, this);
            }


            /// <summary>
            /// Retrieves the set of starting contexts for this node. The starting contexts are the set of Unit[] with a size
            /// equal to the maximum right context size.
            /// </summary>
            /// <returns>the set of starting contexts across nodes.</returns>
            private List<UnitContext> getStartingContexts() 
            {
                if (startingContexts == null) 
                {
                    startingContexts = new List<UnitContext>();
                    // if this is an empty node, the starting context is the set of starting contexts for all successor
                    // nodes, otherwise, it is built up from each pronunciation of this word
                    if (node.isEmpty()) 
                    {
                        GrammarArc[] arcs = getSuccessors();
                        foreach (GrammarArc arc in arcs) 
                        {
                            GState gstate = FlatLinguistParent.getGState(arc.getGrammarNode());
                            startingContexts.AddRange(gstate.getStartingContexts());
                        }
                    } 
                    else 
                    {
  //                    int maxSize = getRightContextSize();
                        IWord word = node.getWord();
                        IPronunciation[] prons = word.getPronunciations(null);
                        foreach (IPronunciation pron in prons) 
                        {
                            UnitContext startingContext = getStartingContext(pron);
                            startingContexts.Add(startingContext);
                        }
                    }
                }
                return startingContexts;
            }


            /**
               /// Retrieves the starting UnitContext for the given pronunciation
                *
               /// @param pronunciation the pronunciation
               /// @return a UnitContext representing the starting context of the pronunciation
                */
            private UnitContext getStartingContext(IPronunciation pronunciation) 
            {
                int maxSize = getRightContextSize();
                IUnit[] units = pronunciation.getUnits();
                IUnit[] context = units.Length > maxSize ? units.Select(x => x).Take(maxSize).ToArray() : units;
                return UnitContext.get(context);
            }


           /// <summary>
           /// Retrieves the set of trailing contexts for this node. the trailing contexts are the set of Unit[] with a size
           /// equal to the maximum left context size that align with the end of the node
           /// </summary>
           /// <returns></returns>
           List<UnitContext> getEndingContexts() 
           {
                List<UnitContext> endingContexts = new List<UnitContext>();
                if (!node.isEmpty()) 
                {
                    int maxSize = getLeftContextSize();
                    IWord word = node.getWord();
                    IPronunciation[] prons = word.getPronunciations(null);
                    foreach (Pronunciation pron in prons) 
                    {
                        IUnit[] units = pron.getUnits();
                        int size = units.Length;
                        IUnit[] context = size > maxSize ? 
                            units.Select(x => x).Skip(size - maxSize).Take(maxSize).ToArray(): units;
                        endingContexts.Add(UnitContext.get(context));
                    }
                }
                return endingContexts;
            }


            /// <summary>
            /// Visit all of the successor states, and gather their starting contexts into this gstates right context
            /// </summary>
            private void pullRightContexts() 
            {
                GrammarArc[] arcs = getSuccessors();
                foreach (GrammarArc arc in arcs) 
                {
                    GState gstate = FlatLinguistParent.getGState(arc.getGrammarNode());
                    rightContexts.AddRange(gstate.getStartingContexts());
                }
            }

            /// <summary>
            /// Returns the set of succesor arcs for this grammar node. If a successor grammar node has no words we'll
            /// substitute the successors for that node (avoiding loops of course)
            /// </summary>
            /// <returns>an array of successors for this GState</returns>
            private GrammarArc[] getSuccessors() 
            {
                return node.getSuccessors();
            }


            /// <summary>
            /// Visit all of the successor states, and push our ending context into the successors left context
            /// </summary>
            void pushLeftContexts() 
            {
                List<UnitContext> endingContext = getEndingContexts();
                List<GrammarNode> visitedSet = new List<GrammarNode>();
                pushLeftContexts(visitedSet, endingContext);
            }


            /// <summary>
            /// Pushes the given left context into the successor states. If a successor state is empty, continue to push into
            /// this empty states successors
            /// </summary>
            /// <param name="visitedSet"></param>
            /// <param name="leftContext">leftContext the context to push</param>
            void pushLeftContexts(List<GrammarNode> visitedSet, List<UnitContext> leftContext) 
            {
                if (visitedSet.Contains(getNode())) 
                {
                    return;
                } 
                else 
                {
                    visitedSet.Add(getNode());
                }

                foreach (GrammarArc arc in getSuccessors()) 
                {
                    GState gstate = FlatLinguistParent.getGState(arc.getGrammarNode());
                    gstate.addLeftContext(leftContext);
                    // if our successor state is empty, also push our
                    // ending context into the empty nodes successors
                    if (gstate.getNode().isEmpty()) {
                        gstate.pushLeftContexts(visitedSet, leftContext);
                    }
                }
            }


            /**
               /// Add the given left contexts to the set of left contexts for this state
                *
               /// @param context the set of contexts to add
                */
            private void addLeftContext(List<UnitContext> context) 
            {
                leftContexts.AddRange(context);
            }


            /**
               /// Adds the given context to the set of left contexts for this state
                *
               /// @param context the context to add
                */
            public void addLeftContext(UnitContext context) 
            {
                leftContexts.Add(context);
            }

            /// <summary>
            /// Returns the entry points for a given context pair
            /// </summary>
            /// <param name="contextPair"></param>
            /// <returns></returns>
            private List<ISearchState> getEntryPoints(ContextPair contextPair) 
            {
                ContextPair contextPairSearch = null;
                foreach(ContextPair cp in entryPoints.Keys)
                    if (cp.Equals(contextPair))
                    {
                        contextPairSearch = cp;
                        break;
                    }
                if (contextPairSearch == null)
                    return null;
                return entryPoints[contextPairSearch];
            }

            /// <summary>
            /// Gets the context-free entry point to this state
            /// </summary>
            /// <returns>the entry point to the state</returns>
            public SentenceHMMState getEntryPoint() 
            {
                // TODO: ideally we'll look for entry points with no left
                // context, but those don't exist yet so we just take
                // the first entry point with an SILENCE left context
                // note that this assumes that the first node in a grammar has a
                // word and that word is a SIL. Not always a valid assumption.

                ContextPair cp = ContextPair.get(UnitContext.SILENCE, UnitContext.SILENCE);
                List<ISearchState> list = getEntryPoints(cp);
                return list == null || list.Count==0 ? null : (SentenceHMMState)list[0];
            }

            /// <summary>
            /// Collects the right contexts for this node and pushes this nodes ending context into the next next set of
            /// nodes.
            /// </summary>
            public void collectContexts() 
            {
                pullRightContexts();
                pushLeftContexts();
            }


            /// <summary>
            /// Expands each GState into the sentence HMM States
            /// </summary>
            public void expand() 
            {
                // for each left context/starting context pair create a list
                // of starting states.
                foreach (UnitContext leftContext in leftContexts) 
                {
                    foreach (UnitContext startingContext in getStartingContexts()) 
                    {
                        ContextPair contextPair = ContextPair.get(leftContext, startingContext);
                        if (!entryPoints.ContainsKey(contextPair))
                            entryPoints.Add(contextPair, new List<ISearchState>());
                    }
                }
                // if this is a final node don't expand it, just create a
                // state and add it to all entry points
                if (node.isFinalNode()) 
                {
                    GrammarState gs = new GrammarState(node);
                    foreach (List<ISearchState> epList in entryPoints.Values) 
                    {
                        epList.Add(gs);
                    }
                } 
                else if (!node.isEmpty()) 
                {
                    // its a full fledged node with a word
                    // so expand it. Nodes without words don't need
                    // to be expanded.
                    foreach (UnitContext leftContext in leftContexts) 
                    {
                        expandWord(leftContext);
                    }
                } 
                else 
                {
                    //if the node is empty, populate the set of entry and exit
                    //points with a branch state. The branch state
                    // branches to the successor entry points for this
                    // state
                    // the exit point should consist of the set of
                    // incoming left contexts and outgoing right contexts
                    // the 'entryPoint' table already consists of such
                    // pairs so we can use that
                    foreach (KeyValuePair<ContextPair, List<ISearchState>> entry in entryPoints) 
                    {
                        ContextPair cp = entry.Key;
                        List<ISearchState> epList = entry.Value;
                        SentenceHMMState bs = new BranchState(cp.getLeftContext().ToString(),
                                cp.getRightContext().ToString(), node.getID());
                        epList.Add(bs);
                        addExitPoint(cp, bs);
                    }
                }
                addEmptyEntryPoints();
            }


            /**
               /// Adds the set of empty entry points. The list of entry points are tagged with a context pair. The context pair
               /// represent the left context for the state and the starting context for the state, this allows states to be
               /// hooked up properly. However, we may be transitioning from states that have no right hand context (CI units
               /// such as SIL fall into this category). In this case we'd normally have no place to transition to since we add
               /// entry points for each starting context. To make sure that there are entry points for empty contexts if
               /// necessary, we go through the list of entry points and find all left contexts that have a right hand context
               /// size of zero. These entry points will need an entry point with an empty starting context. These entries are
               /// synthesized and added to the the list of entry points.
                */
            private void addEmptyEntryPoints() 
            {
                Dictionary<ContextPair, List<ISearchState>> emptyEntryPoints = new Dictionary<ContextPair, List<ISearchState>>();
                foreach (KeyValuePair<ContextPair, List<ISearchState>> entry in entryPoints) 
                {
                    ContextPair cp = entry.Key;
                    if (needsEmptyVersion(cp)) 
                    {
                        ContextPair emptyContextPair = ContextPair.get(cp.getLeftContext(), UnitContext.EMPTY);
                        List<ISearchState> epList=null;
                        if (!emptyEntryPoints.ContainsKey(emptyContextPair)) 
                        {
                            epList = new List<ISearchState>();
                            emptyEntryPoints.Add(emptyContextPair, epList);
                        }
                        epList = emptyEntryPoints[emptyContextPair];
                        epList.AddRange(entry.Value);
                    }
                }
                entryPoints.Concat(emptyEntryPoints);
            }


            /**
               /// Determines if the context pair needs an empty version. A context pair needs an empty version if the left
               /// context has a max size of zero.
                *
               /// @param cp the contex pair to check
               /// @return <code>true</code> if the pair needs an empt version
                */
            private Boolean needsEmptyVersion(ContextPair cp) 
            {
                UnitContext left = cp.getLeftContext();
                IUnit[] units = left.getUnits();
                return units.Length > 0 && (getRightContextSize(units[0]) < getRightContextSize());

            }


            /**
               /// Returns the grammar node of the gstate
                *
               /// @return the grammar node
                */
            private GrammarNode getNode() 
            {
                return node;
            }


            /**
               /// Expand the the word given the left context
                *
               /// @param leftContext the left context
                */
            private void expandWord(UnitContext leftContext) 
            {
                IWord word = node.getWord();
                FlatLinguistParent.T("Expanding word " + word + " for lc " + leftContext);
                IPronunciation[] pronunciations = word.getPronunciations(null);
                for (int i = 0; i < pronunciations.Length; i++) 
                {
                    expandPronunciation(leftContext, pronunciations[i], i);
                }
            }


            /**
               /// Expand the pronunciation given the left context
                *
               /// @param leftContext   the left context
               /// @param pronunciation the pronunciation to expand
               /// @param which         unique ID for this pronunciation
                */
            // Each GState maintains a list of entry points. This list of
            // entry points is used when connecting up the end states of
            // one GState to the beginning states in another GState. The
            // entry points are tagged by a ContextPair which represents
            // the left context upon entering the state (the left context
            // of the initial units of the state), and the right context
            // of the previous states (corresponding to the starting
            // contexts for this state).
            //
            // When expanding a pronunciation, the following steps are
            // taken:
            //      1) Get the starting context for the pronunciation.
            //      This is the set of units that correspond to the start
            //      of the pronunciation.
            //
            //      2) Create a new PronunciationState for the
            //      pronunciation.
            //
            //      3) Add the PronunciationState to the entry point table
            //      (a hash table keyed by the ContextPair(LeftContext,
            //      StartingContext).
            //
            //      4) Generate the set of context dependent units, using
            //      the left and right context of the GState as necessary.
            //      Note that there will be fan out at the end of the
            //      pronunciation to allow for units with all of the
            //      various right contexts. The point where the fan-out
            //      occurs is the (length of the pronunciation - the max
            //      right context size).
            //
            //      5) Attach each cd unit to the tree
            //
            //      6) Expand each cd unit into the set of HMM states
            //
            //      7) Attach the optional and looping back silence cd
            //      unit
            //
            //      8) Collect the leaf states of the tree and add them to
            //      the exitStates list.
            private void expandPronunciation(UnitContext leftContext,
                                                IPronunciation pronunciation, int which) 
            {
                UnitContext startingContext = getStartingContext(pronunciation);
                // Add the pronunciation state to the entry point list
                // (based upon its left and right context)
                String pname = "P(" + pronunciation.getWord() + '[' + leftContext
                        + ',' + startingContext + "])-G" + getNode().getID();
                PronunciationState ps = new PronunciationState(pname, pronunciation, which);
                FlatLinguistParent.T("     Expanding " + ps.getPronunciation() + " for lc " + leftContext);
                ContextPair cp = ContextPair.get(leftContext, startingContext);

                ContextPair cpRez = null;
                foreach(ContextPair iterator in entryPoints.Keys)
                    if (iterator.Equals(cp)) 
                    {
                        cpRez = iterator;
                        break;
                    }
                ///not applay the Equl operator 
                if (cpRez==null)
                {
                    throw new Exception("No EP list for context pair " + cp);
                }
                List<ISearchState> epList = entryPoints[cpRez];
                if (epList != null) 
                {
                    epList.Add(ps);
                }
                IUnit[] units = pronunciation.getUnits();
                int fanOutPoint = units.Length - getRightContextSize();
                if (fanOutPoint < 0) {
                    fanOutPoint = 0;
                }
                SentenceHMMState tail = ps;
                for (int i = 0; tail != null && i < fanOutPoint; i++) {
                    tail = attachUnit(ps, tail, units, i, leftContext, UnitContext.EMPTY);
                }
                SentenceHMMState branchTail = tail;
                foreach (UnitContext finalRightContext in rightContexts) 
                {
                    tail = branchTail;
                    for (int i = fanOutPoint; tail != null && i < units.Length; i++) {
                        tail = attachUnit(ps, tail, units, i, leftContext, finalRightContext);
                    }
                }
            }


            /**
               /// Attaches the given unit to the given tail, expanding the unit if necessary. If an identical unit is already
               /// attached, then this path is folded into the existing path.
                *
               /// @param parent       the parent state
               /// @param tail         the place to attach the unit to
               /// @param units        the set of units
               /// @param which        the index into the set of units
               /// @param leftContext  the left context for the unit
               /// @param rightContext the right context for the unit
               /// @return the tail of the added unit (or null if the path was folded onto an already expanded path.
                */
            private SentenceHMMState attachUnit(PronunciationState parent,
                                                SentenceHMMState tail, IUnit[] units, int which,
                                                UnitContext leftContext, UnitContext rightContext) 
            {
                IUnit[] lc = getLC(leftContext, units, which);
                IUnit[] rc = getRC(units, which, rightContext);
                UnitContext actualRightContext = UnitContext.get(rc);
                LeftRightContext context = LeftRightContext.get(lc, rc);
                Unit cdUnit = FlatLinguistParent.unitManager.getUnit(units[which].getName(), units[which].isFiller(), context);
                UnitState unitState = new ExtendedUnitState(parent, which, cdUnit);
                float logInsertionProbability;
                if (unitState.getUnit().isSilence()) 
                {
                    logInsertionProbability = FlatLinguistParent.logSilenceInsertionProbability;
                } 
                else if (unitState.getUnit().isFiller()) 
                {
                    logInsertionProbability = FlatLinguistParent.logFillerInsertionProbability;
                } 
                else if (unitState.getWhich() == 0) 
                {
                    logInsertionProbability = FlatLinguistParent.logWordInsertionProbability;
                }
                else 
                {
                    logInsertionProbability = FlatLinguistParent.logUnitInsertionProbability;
                }
                // check to see if this state already exists, if so
                // branch to it and we are done, otherwise, branch to
                // the new state and expand it.
                SentenceHMMState existingState = getExistingState(unitState);
                if (existingState != null) 
                {
                    attachState(tail, existingState, logOne, logInsertionProbability);
                    // T(" Folding " + existingState);
                    return null;
                } 
                else 
                {
                    attachState(tail, unitState, logOne, logInsertionProbability);
                    addStateToCache(unitState);
                    // T(" Attaching " + unitState);
                    tail = expandUnit(unitState);
                    // if we are attaching the last state of a word, then
                    // we add it to the exitPoints table. the exit points
                    // table is indexed by a ContextPair, consisting of
                    // the exiting left context and the right context.
                    if (unitState.isLast()) {
                        UnitContext nextLeftContext = generateNextLeftContext(leftContext, units[which]);
                        ContextPair cp = ContextPair.get(nextLeftContext, actualRightContext);
                        // T(" Adding to exitPoints " + cp);
                        addExitPoint(cp, tail);
                    }
                    return tail;
                }
            }


            /// <summary>
            /// Adds an exit point to this gstate
            /// </summary>
            /// <param name="cp">the context tag for the state</param>
            /// <param name="state">the state associated with the tag</param>
            private void addExitPoint(ContextPair cp, SentenceHMMState state) 
            {
                List<ISearchState> listAdd = null;
                foreach (ContextPair cpIterator in exitPoints.Keys)
                    if (cpIterator.Equals(cp))
                    {
                        listAdd = exitPoints[cpIterator];
                        break;
                    }

                if (listAdd==null)
                {
                    listAdd = new List<ISearchState>();
                    exitPoints.Add(cp, listAdd);
                }

                listAdd.Add(state);
            }

            /**
               /// Get the left context for a unit based upon the left context size, the entry left context and the current
               /// unit.
                *
               /// @param left  the entry left context
               /// @param units the set of units
               /// @param index the index of the current unit

                */
            private IUnit[] getLC(UnitContext left, IUnit[] units, int index) {
                IUnit[] leftUnits = left.getUnits();
                int curSize = leftUnits.Length + index;
                int actSize = Math.Min(curSize, getLeftContextSize(units[index]));
                int leftIndex = index - actSize;
            
                IUnit[] lc = new Unit[actSize];
                for (int i = 0; i < lc.Length; i++) {
                    int lcIndex = leftIndex + i;
                    if (lcIndex < 0) {
                        lc[i] = leftUnits[leftUnits.Length + lcIndex];
                    } else {
                        lc[i] = units[lcIndex];
                    }
                }
                return lc;
            }

            /**
               /// Get the right context for a unit based upon the right context size, the exit right context and the current
               /// unit.
                *
               /// @param units the set of units
               /// @param index the index of the current unit
               /// @param right the exiting right context

                */
            private IUnit[] getRC(IUnit[] units, int index, UnitContext right) {
                IUnit[] rightUnits = right.getUnits();
                int leftIndex = index + 1;
                int curSize = units.Length - leftIndex + rightUnits.Length;
                int actSize = Math.Min(curSize, getRightContextSize(units[index]));

                IUnit[] rc = new Unit[actSize];
                for (int i = 0; i < rc.Length; i++) {
                    int rcIndex = leftIndex + i;
                    if (rcIndex < units.Length) {
                        rc[i] = units[rcIndex];                    
                    } else {
                        rc[i] = rightUnits[rcIndex - units.Length];
                    }
                }
                return rc;
            }

            /**
               /// Gets the maximum context size for the given unit
                *
               /// @param unit the unit of interest
               /// @return the maximum left context size for the unit
                */
            private int getLeftContextSize(IUnit unit) {
                return unit.isFiller() ? 0 : getLeftContextSize();
            }


            /**
               /// Gets the maximum context size for the given unit
                *
               /// @param unit the unit of interest
               /// @return the maximum right context size for the unit
                */
            private int getRightContextSize(IUnit unit) {
                return unit.isFiller() ? 0 : getRightContextSize();
            }


            /**
               /// Returns the size of the left context.
                *
               /// @return the size of the left context
                */
            protected int getLeftContextSize() 
            {
                return FlatLinguistParent.acousticModel.getLeftContextSize();
            }

            /// <summary>
            /// Returns the size of the right context.
            /// </summary>
            /// <returns>the size of the right context</returns>
            protected int getRightContextSize() 
            {
                return FlatLinguistParent.acousticModel.getRightContextSize();
            }

            /// <summary>
            /// Generates the next left context based upon a previous context and a unit
            /// </summary>
            /// <param name="prevLeftContext">the previous left context</param>
            /// <param name="unit">the current unit</param>
            /// <returns></returns>
            UnitContext generateNextLeftContext(UnitContext prevLeftContext, IUnit unit) 
            {
                IUnit[] prevUnits = prevLeftContext.getUnits();
                int actSize = Math.Min(prevUnits.Length, getLeftContextSize());
                if (actSize == 0)
                    return UnitContext.EMPTY;
                IUnit[] leftUnits = new Unit[actSize + 1];
                Array.Copy(prevUnits, 1, leftUnits, 0, Math.Min(prevUnits.Length-1, actSize + 1));
                ///    Arrays.copyOfRange(prevUnits, 1, actSize + 1);
                leftUnits[actSize - 1] = unit;
                return UnitContext.get(leftUnits);
            }
            

            /**
               /// Expands the unit into a set of HMMStates. If the unit is a silence unit add an optional loopback to the
               /// tail.
                *
               /// @param unit the unit to expand
               /// @return the head of the hmm tree
                */
            protected SentenceHMMState expandUnit(UnitState unit) {
                SentenceHMMState tail = getHMMStates(unit);
                // if the unit is a silence unit add a loop back from the
                // tail silence unit
                if (unit.getUnit().isSilence()) {
                    // add the loopback, but don't expand it // anymore
                    attachState(tail, unit, logOne, FlatLinguistParent.logSilenceInsertionProbability);
                }
                return tail;
            }


            /**
               /// Given a unit state, return the set of sentence hmm states associated with the unit
                *
               /// @param unitState the unit state of intereset
               /// @return the hmm tree for the unit
                */
            private HMMStateState getHMMStates(UnitState unitState) 
            {
                HMMStateState hmmTree;
                HMMStateState finalState;
                IUnit unit = unitState.getUnit();
                HMMPosition position = unitState.getPosition();
                IHMM hmm = FlatLinguistParent.acousticModel.lookupNearestHMM(unit, position, false);
                IHMMState initialState = hmm.getInitialState();
                hmmTree = new HMMStateState(unitState, initialState);
                attachState(unitState, hmmTree, logOne, logOne);
                addStateToCache(hmmTree);
                finalState = expandHMMTree(unitState, hmmTree);
                return finalState;
            }


            /**
               /// Expands the given hmm state tree
                *
               /// @param parent the parent of the tree
               /// @param tree   the tree to expand
               /// @return the final state in the tree
                */
            private HMMStateState expandHMMTree(UnitState parent, HMMStateState tree) {
                HMMStateState retState = tree;
                foreach (HMMStateArc arc in tree.getHMMState().getSuccessors()) 
                {
                    HMMStateState newState;
                    if (arc.getHMMState().isEmitting()) {
                        newState = new HMMStateState(parent, arc.getHMMState());
                    } else {
                        newState = new NonEmittingHMMState(parent, arc.getHMMState());
                    }
                    SentenceHMMState existingState = getExistingState(newState);
                    float logProb = arc.getLogProbability();
                    if (existingState != null) {
                        attachState(tree, existingState, logOne, logProb);
                    } else {
                        attachState(tree, newState, logOne, logProb);
                        addStateToCache(newState);
                        retState = expandHMMTree(parent, newState);
                    }
                }
                return retState;
            }


            /// <summary>
            /// Connect up all of the GStates. Each state now has a table of exit points. These exit points represent tail
            /// states for the node. Each of these tail states is tagged with a ContextPair, that indicates what the left
            /// context is (the exiting context) and the right context (the entering context) for the transition. To connect
            /// up a state, the connect does the following: 
            /// 1) Iterate through all of the grammar successors for this state
            /// 2) Get the 'entry points' for the successor that match the exit points. 
            /// 3) Hook them up.
            /// 
            /// Note that for a task with 1000 words this will involve checking on the order of 35,000,000 connections and
            /// making about 2,000,000 connections
            /// </summary>
            public void connect() 
            {
                // T("Connecting " + node.getWord());
                foreach (GrammarArc arc in getSuccessors()) 
                {
                    GState gstate = FlatLinguistParent.getGState(arc.getGrammarNode());
                    if (!gstate.getNode().isEmpty()
                            && gstate.getNode().getWord().getSpelling().Equals(IDictionary.SENTENCE_START_SPELLING)) {
                        continue;
                    }
                    float probability = arc.getProbability();
                    // adjust the language probability by the number of
                    // pronunciations. If there are 3 ways to say the
                    // word, then each pronunciation gets 1/3 of the total
                    // probability.
                    if (FlatLinguistParent.spreadWordProbabilitiesAcrossPronunciations && !gstate.getNode().isEmpty())
                    {
                        int numPronunciations = gstate.getNode().getWord().getPronunciations(null).Length;
                        probability -= FlatLinguistParent.logMath.linearToLog(numPronunciations);
                    }
                    float fprob = probability;
                    foreach (KeyValuePair<ContextPair, List<ISearchState>> entry in exitPoints) 
                    {
                        List<ISearchState> destEntryPoints = gstate.getEntryPoints(entry.Key);
                        if (destEntryPoints != null) {
                            List<ISearchState> srcExitPoints = entry.Value;
                            connect(srcExitPoints, destEntryPoints, fprob);
                        }
                    }
                }
            }


            /// <summary>
            /// connect all the states in the source list to the states in the destination list
            /// </summary>
            /// <param name="sourceList">the set of source states</param>
            /// <param name="destList">the set of destination states.</param>
            /// <param name="logLangProb"></param>
            private void connect(List<ISearchState> sourceList, List<ISearchState> destList, float logLangProb) 
            {
                foreach (ISearchState source in sourceList) 
                {
                    SentenceHMMState sourceState = (SentenceHMMState) source;
                    foreach (ISearchState dest in destList) 
                    {
                        SentenceHMMState destState = (SentenceHMMState) dest;
                        sourceState.connect(FlatLinguistParent.getArc(destState, logLangProb, logOne));
                        exitConnections++;
                    }
                }
            }

            /**
               /// Attaches one SentenceHMMState as a child to another, the transition has the given probability
                *
               /// @param prevState              the parent state
               /// @param nextState              the child state
               /// @param logLanguageProbablity  the language probability of transition in the LogMath log domain
               /// @param logInsertionProbablity insertion probability of transition in the LogMath log domain
                */
            protected void attachState(SentenceHMMState prevState,
                                        SentenceHMMState nextState,
                                        float logLanguageProbablity, 
                                        float logInsertionProbablity) 
            {
                prevState.connect(FlatLinguistParent.getArc(nextState,
                        logLanguageProbablity, logInsertionProbablity));
                if (FlatLinguistParent.showCompilationProgress && FlatLinguistParent.totalStateCounter++ % 1000 == 0) 
                {
                    Trace.WriteLine(".");
                }
            }


            /**
               /// Returns all of the states maintained by this gstate
                *
               /// @return the set of all states
                */
            public List<ISearchState> getStates() 
            {
                // since pstates are not placed in the cache we have to
                // gather those states. All other states are found in the
                // existingStates cache.
                List<ISearchState> allStates = new List<ISearchState>(existingStates.Values);
                foreach (List<ISearchState> list in entryPoints.Values) 
                {
                    allStates.AddRange(list);
                }
                return allStates;
            }


            /**
               /// Checks to see if a state that matches the given state already exists
                *
               /// @param state the state to check
               /// @return true if a state with an identical signature already exists.
                */
            private SentenceHMMState getExistingState(SentenceHMMState state) 
            {
                String sign = state.getSignature();
                if (!existingStates.ContainsKey(sign))
                    return null;
                return existingStates[sign];
            }


            /**
               /// Adds the given state to the cache of states
                *
               /// @param state the state to add
                */
            private void addStateToCache(SentenceHMMState state) 
            {
                existingStates.Add(state.getSignature(), state);
            }


            /**
               /// Prints info about this GState
                */
            public void dumpInfo() {
                Trace.WriteLine(" ==== " + this + " ========");
                Trace.WriteLine("Node: " + node);
                if (node.isEmpty()) {
                    Trace.WriteLine("  (Empty)");
                } else {
                    Trace.WriteLine(" " + node.getWord());
                }
                Trace.WriteLine(" ep: " + entryPoints.Count);
                Trace.WriteLine(" exit: " + exitPoints.Count);
                Trace.WriteLine(" cons: " + exitConnections);
                Trace.WriteLine(" tot: " + getStates().Count);
                Trace.WriteLine(" sc: " + getStartingContexts().Count);
                Trace.WriteLine(" rc: " + leftContexts.Count);
                Trace.WriteLine(" lc: " + rightContexts.Count);
                dumpDetails();
            }


            /**
               /// Dumps the details for a gstate
                */
            void dumpDetails() {
                //dumpCollection(" entryPoints", (List<Object>)(entryPoints.Keys));
                //dumpCollection(" entryPoints states", entryPoints.Values);
                //dumpCollection(" exitPoints", exitPoints.Keys);
                //dumpCollection(" exitPoints states", exitPoints.Values);
                //dumpNextNodes();
                //dumpExitPoints(exitPoints.Values);
                //dumpCollection(" startingContexts", getStartingContexts());
                //dumpCollection(" branchingInFrom", leftContexts);
                //dumpCollection(" branchingOutTo", rightContexts);
                //dumpCollection(" existingStates", existingStates.Keys);
            }


            /**
               /// Dumps out the names of the next set of grammar nodes
                */
            private void dumpNextNodes() 
            {
                Trace.WriteLine("     Next Grammar Nodes: ");
                foreach (GrammarArc arc in node.getSuccessors()) 
                {
                    Trace.WriteLine("          " + arc.getGrammarNode());
                }
            }


            /**
               /// Dumps the exit points and their destination states
                *
               /// @param eps the collection of exit points
                */
            private void dumpExitPoints(List<List<ISearchState>> eps) 
            {
                foreach (List<ISearchState> epList in eps) 
                {
                    foreach (ISearchState state in epList) 
                    {
                        Trace.WriteLine("      Arcs from: " + state);
                        foreach (ISearchStateArc arc in state.getSuccessors()) 
                        {
                            Trace.WriteLine("          " + arc.getState());
                        }
                    }
                }
            }


            /**
               /// Dumps the given collection
                *
               /// @param name       the name of the collection
               /// @param collection the collection to dump
                */
            private void dumpCollection(String name, List<Object> collection) 
            {
                Trace.WriteLine("     " + name);
                foreach (Object obj in collection) {
                    Trace.WriteLine("         " + obj);
                }
            }
            /**
               /// Returns the string representation of the object
                *
               /// @return the string representation of the object
                */
            override public String ToString() 
            {
                if (node.isEmpty()) {
                    return "GState " + node + "(empty)";
                } else {
                    return "GState " + node + " word " + node.getWord();
                }
            }
        }
    }
}
